package algoritmos;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import java.util.TreeSet;

import modelo.Aresta;
import modelo.Grafo;
import modelo.Vertice;

public class Prim {
	public static void prim(Grafo g){
		if(g!=null && g.getVertices().size()!=0){
			Vertice vInicial = g.getVertices().get(0);
			
			Set<Vertice> listaDeVerticesFinal = new HashSet<Vertice>();
			listaDeVerticesFinal.add(vInicial);
			
			List<Aresta> listaDeArestaFinal = new ArrayList<Aresta>();
			
			TreeSet<Aresta> listaArestasSeguras = new TreeSet<Aresta>(new Comparator<Aresta>() {
				@Override
				public int compare(Aresta o1, Aresta o2) {
					if(o1.getPeso() > o2.getPeso()){
						return 1;
					}else if (o1.getPeso() < o2.getPeso()){
						return -1;
					}else{
						return 0;
					}
				}
			});
			
			while(listaDeVerticesFinal.size()<g.getVertices().size()){
				listaArestasSeguras.clear();
				
				for (Vertice v : listaDeVerticesFinal) {
					for(Aresta a : v.getArestasAdj()){
						//se a aresta nao ligar dois vertices da lista final
						if( !(listaDeVerticesFinal.contains(a.getOrigem()) && listaDeVerticesFinal.contains(a.getDestino())) ){
							listaArestasSeguras.add(a);
						}
					}
				}
				if(listaArestasSeguras.size()!=0){
					Aresta firstA = listaArestasSeguras.first();
					if(!listaDeArestaFinal.contains(firstA)){
						listaDeArestaFinal.add(firstA);
						listaDeVerticesFinal.add(firstA.getDestino());
						listaDeVerticesFinal.add(firstA.getOrigem());
					}
				}else{
					break;
				}
			}
		}else{
			System.out.println("BOOM");
		}
	}
}
